package com.adamjwh.sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 
 * @author adamjwh
 *
 * 算法描述：
 * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 按增量序列个数k，对序列进行k 趟排序；
 * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 * 
 * 最佳情况：T(n) = O(nlog2 n)  最坏情况：T(n) = O(nlog2 n)  平均情况：T(n) =O(nlog n)　
 */
public class ShellSort {
	
	public void shellSort(int[] array) {
        int len = array.length;  
        int gap = 1;	//增量
        int preIndex, current;
        
        while (gap < len/3) {	//动态定义间隔序列
			gap = gap * 3 + 1;
		}
        
        while (gap > 0) {
        	for (int i=gap; i<len; i++) {
        		preIndex = i - gap;
        		current = array[i];
        		while (preIndex >= 0 && array[preIndex] > current) {
        			array[preIndex+gap] = array[preIndex];
        			preIndex -= gap;
        		}
        		array[preIndex+gap] = current;
        	}
        	gap = (gap - 1) / 3;
        }
	}
	
	public static void main(String[] args) {
		int[] arr = {10,15,25,37,21,13,9,10,15,2};
		ShellSort shellSort = new ShellSort();
		shellSort.shellSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
}
